package com.example.demo.leetcode.classics150;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * ******************************************************
 *
 * @author liugh9
 * @version 1.0
 * @classname _24文本左右对齐
 * @description
 * @date 2023/07/15 9:25
 * <p>
 * ******************************************************
 */
public class _24文本左右对齐 {

    public List<String> fullJustify(String[] words, int maxWidth) {
        int length = words.length;
        int rowLength = 0;
        int start = 0;
        List<String> res = new LinkedList<>();
        for (int i = 0; i < length; i++) {
            rowLength += words[i].length() + 1;
            if (i == length - 1) {
                // 处理最后一行
                dealRow(res, words, start, i, rowLength, maxWidth, true);
                continue;
            }
            if (rowLength + words[i + 1].length() > maxWidth) {
                // 处理第一行
                dealRow(res, words, start, i, rowLength, maxWidth, false);
                // 重置rowLength
                rowLength = 0;
                start = i + 1;
            }
        }
        return res;
    }

    private void dealRow(List<String> res, String[] words, int start, int end, int rowLength, int maxWidth, boolean isLast) {
        // 该行单词个数
        int num = end - start + 1;
        // 最大字数-之前计算的字数+多计算的空格数 = 总共格数
        int blankNum = maxWidth - rowLength + num;
        if (num == 1) {
            StringBuilder row = new StringBuilder(words[start]);
            setBlank(row, blankNum);
            res.add(row.toString());
            return;
        }

        // 平均空格
        int i;
        // 剩余空格
        int j;
        int[] blanks = new int[num];
        if (isLast) {
            i = 0;
            j = num - 1;
        } else {
            i = blankNum / (num - 1);
            j = blankNum % (num - 1);
            Arrays.fill(blanks, i);
        }
        while (j > 0) {
            blanks[--j]++;
        }
        if (isLast) {
            // 最后一个空格
            blanks[num - 1] = blankNum - num + 1;
        } else {
            // 最后一个单词没有空格
            blanks[num - 1] = 0;
        }
        StringBuilder row = new StringBuilder();
        for (int k = start; k <= end; k++) {
            setBlank(row.append(words[k]), blanks[k - start]);
        }
        res.add(row.toString());
    }


    private void setBlank(StringBuilder row, int blankNum) {
        for (int i = 0; i < blankNum; i++) {
            row.append(' ');
        }
    }
}
